package com.dataStructure.树.二叉搜索树;

import com.dataStructure.树.printer.BinaryTreeInfo;

import java.util.LinkedList;

@SuppressWarnings("all")
public class 二叉搜索树_BinarySearchTree<E /*extends Comparable<E>*/> implements BinaryTreeInfo {
    //节点个数
    private int size;
    //根节点属性
    private Node<E> root;
    //传入比较器
    private java.util.Comparator<E> comparator;

    public 二叉搜索树_BinarySearchTree() {
        this(null);
    }

    public 二叉搜索树_BinarySearchTree(java.util.Comparator<E> comparator) {
        this.comparator = comparator;
    }

    //构造函数
    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        //是否是叶子节点
        public boolean isLeaf() {
            return left == null && right == null;
        }

        //是否有两个度
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
    }

    //用于传递遍历逻辑的接口
    public static /*interface*/ abstract class Visitor<E> {
        //要定义成员变量，就不能是接口，变成抽象类
        boolean stop;

        //方法返回true，就代表停止遍历
        abstract boolean visit(E element);
    }

    //中序 自定义遍历接口
    public void inorder(Visitor<E> visitor) {
        if (visitor == null) return;
        inorder(root, visitor);
    }

    private void inorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;

        inorder(node.left, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorder(node.right, visitor);
    }

    //后序 自定义遍历接口
    public void postorder(Visitor<E> visitor) {
        if (visitor == null) return;
        postorder(root, visitor);
    }

    private void postorder(Node<E> node, Visitor<E> visitor) {
        //这里的visitor.stop是防止程序继续递归调用
        if (node == null || visitor.stop) return;

        postorder(node.left, visitor);
        postorder(node.right, visitor);
        //这里的visitor.stop是防止
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    //层序  自定义遍历接口
    public void levelOrder(Visitor<E> visitor) {
        java.util.Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();

            //System.out.println(node.element);
            //遍历元素的逻辑由传入的visitor决定
            boolean visit = visitor.visit(node.element);
            if (visit) break;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    //前序  自定义遍历接口
    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root, visitor);
    }

    private void preorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        //System.out.println(node.element);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }

    // 元素的数量
    public int size() {
        return this.size;
    }

    // 是否为空
    public boolean isEmpty() {
        return this.size == 0;
    }

    // 清空所有元素
    public void clear() {

    }

    // 添加元素
    public void add(E element) {
        elemenrNonullCheck(element);

        //一开始什么都没有，添加的那一个节点为根节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        //添加的不是第一个节点
        //1.找到父节点 parent,与他进行比较

        //从根节点开始比较
        Node<E> node = root;

        //默认情况让根节点作为父节点
        Node<E> parent = root;

        //需要保存最后一次比较的结果，以确定是left，还是right
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            //在这里保存一下父节点
            parent = node;
            if (cmp > 0) {
                //拿到右节点接着比较
                node = node.right;
            } else if (cmp < 0) {
                //拿到左节点接着比较
                node = node.left;
            } else {//相等
                node.element = element;
                return;
            }
        }

        //2.创建新节点 node
        //看看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);
        //3.parent.left = node 或者 parent.right = node
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }

    // 删除元素,调用删除节点的remove方法
    public void remove(E element) {
        remove(node(element));
    }
    //删除元素在内部即为删除节点
    private void remove(Node<E> node) {
        if (node == null) return;
        //能来到这里，说明节肯定不为空，首先size--
        size--;
        //优先处理度为2的
        if (node.hasTwoChildren()){
            //找到这个节点的后继节点
            Node<E> s = successor(node);
            //用后继节点取代这个要删除的节点
            node.element = s.element;
            //再把node节点的指针指向这个后继节点，因为这个节点的度只可能是1或0，删除1或0的操作后面统一进行
            node = s;
        }
        //看看这个要删除的节点的度为1还是0
        Node<E> replaceNode = node.left != null ? node.left:node.right;
        //度为1
        if (replaceNode != null){
            //将node的那一个子节点的父指针指向node的父节点
            replaceNode.parent = node.parent;
            ////如果要删除的节点为根节点
            if (node.parent == null){
                root = replaceNode;
                //如果要删除的节点在其父节点的左边
            }else if (node == node.parent.left) {
                node.parent.left = replaceNode;
                //如果要删除的节点在其父节点的右边
            }else if (node == node.parent.right){
                node.parent.right = replaceNode;
            }
        //度为0
        }else{
            //要删的节点为根节点
            if (node.parent == null){
                root = null;
                //如果在左边
            } else if (node == node.parent.left){
                node.parent.left = null;
                //如果在右边
            }else if (node == node.parent.right){
                node.parent.right = null;
            }
        }
    }
    //要删除这个节点首先要找到这个节点
    private Node<E> node(E element) {
        Node<E> node = root;
        while (node != null) {
            int cmp = compare(node.element, element);
            if (cmp == 0) return node;
            if (cmp < 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    //搜索元素
    public boolean contains(E element) {
        return node(element) != null;
    }

    //比较方法
    //返回值等于0，代表e1和e2相等
    //返回值大于0，代表e1大于e2
    //返回值小于0，代表e1小于e2
    private int compare(E e1, E e2) {
        //第一种传入比较器实现比较的时候
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        //如果没有传入比较器，那么我认为传入的元素已经遵守了Comparable接口，调用这个里面的比较逻辑
        return ((java.lang.Comparable<E>) e1).compareTo(e2);
    }

    //检测element不能为空
    private void elemenrNonullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element not be null");
        }
    }

    //找到节点的前驱节点
    private Node<E> predesessor(Node<E> node) {
        //如果节点为空，没有前驱
        if (node == null) return null;

        //第一种情况
        //如果左边不等于空，意味着从左子树里面去找前驱
        //前驱节点在左子树当中（left.right.right.right... ）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        //第二种情况
        //从父节点，父节点的父节点....中寻找前驱节点
        //当node没有父节点，或者node是它父节点的右子树跳出循环
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        //node.parent == null;
        //node == node.parent.right;
        //循环退出就返回parent
        return node.parent;
    }

    //找到节点的后继节点
    private Node<E> successor(Node<E> node) {
        //如果节点为空，没有前驱
        if (node == null) return null;

        //第一种情况
        //如果右边不等于空，意味着从右子树里面去找后继
        //后继节点在右子树当中（right.left.left.left... ）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        //第二种情况
        //从父节点，父节点的父节点....中寻找后继节点
        //当node没有父节点，或者node是它父节点的左子树跳出循环
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        //node.parent == null;
        //node == node.parent.right;
        //循环退出就返回parent
        return node.parent;
    }

    //获得二叉树的高度
    public int height() {
        return height(root);
    }

    //获取某一个节点的高度（递归）
    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.right), height(node.left));
    }

    //层序遍历获得二叉树的高度（迭代）
    public int height1() {
        if (root == null) return 0;
        int height = 0;

        java.util.Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        //代表某一层的元素的数量
        int levelSize = 1;

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //当元素出队一个，levelSize就减一
            levelSize--;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            //当元素减为0之后，代表这一层已经访问完毕
            //队列里面的元素就是下一层的元素的个数，将个数赋值给levelSize
            //同时height即队列高度加一
            if (levelSize == 0) {
                levelSize = queue.size();
                height++;
            }
        }
        return height;

    }

    //层序遍历1 判断一棵树是否为完全二叉树
    public boolean isComplete() {
        if (root == null) return false;

        java.util.Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;

            //如果左右都不为空，正常遍历
            if (node.hasTwoChildren()) {
                queue.offer(node.left);
                queue.offer(node.right);
                //如果左为空，右不为空说明根本不是完全二叉树。直接返回false
            } else if (node.left == null && node.right != null) {
                return false;
                //如果是左右为空，或左不为空右为空，则接下来的节点必修是叶子节点
            } else {
                leaf = true;
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }

    //层序遍历2 判断一棵树是否为完全二叉树
    public boolean isComplete1() {
        if (root == null) return false;

        java.util.Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                //node.left == null && node.right != null;
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                leaf = true;
            }
        }
        return true;
    }

/*
    //前序遍历
    public void preorderTraversal() {
        preorderTraversal(root);
    }

    private void preorderTraversal(Node<E> node) {
        if (node == null) return;
        System.out.println(node.element);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    //中序遍历  遍历的元素可以是从小到大或者从大到小
    public void inorderTraversal() {
        inorderTraversal(root);
    }

    //升序排列
    private void inorderTraversal(Node<E> node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.println(node.element);
        inorderTraversal(node.right);
    }

    //后序遍历
    public void postorderTraversal() {
        postorderTraversal(root);
    }

    private void postorderTraversal(Node<E> node) {
        if (node == null) return;
        preorderTraversal(node.left);
        preorderTraversal(node.right);
        System.out.println(node.element);
    }

    //层序遍历
    public void levelOrderTraversal() {
        if (root == null) return;
        levelOrderTraversal(root);
    }

    //这里使用自己写的队列来实现层序遍历
    private void levelOrderTraversal(Node<E> node) {
        Queue<Node<E>> queue = new Queue<>();
        queue.enQueue(node);
        Node<E> head = node;
        while (!queue.isEmpty()) {
            head = queue.front();
            System.out.println(head.element);
            queue.deQueue();
            if (head.left != null) {
                queue.enQueue(head.left);
            }
            if (head.right != null) {
                queue.enQueue(head.right);
            }
        }
    }

    //这里使用jdk官方提供的队列来实现层序遍历
    public void lelevelOrderTraversal_jdk() {
        java.util.Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            System.out.println(node.element);

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
*/

    //利用前序遍历树状打印二叉搜索树
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        toString(root, sb, "");
        return sb.toString();
    }

    private void toString(Node<E> node, StringBuilder sb, String prifix) {
        if (node == null) return;

        sb.append(prifix).append(node.element).append("\n");
        toString(node.left, sb, "L---");
        toString(node.right, sb, "R---");
    }

    //用来看看二叉树长什么样子
    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
            return myNode.element + "_p(" + parentString + ")";
        }
        return ((Node<E>) node).element;
    }
}
